{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #The k Strongest Values in an Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #two-pointers #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #双指针 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: getStrongest"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #数组中的 k 个最强值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>arr</code> 和一个整数 <code>k</code> 。</p>\n",
    "\n",
    "<p>设 <code>m</code> 为数组的中位数，只要满足下述两个前提之一，就可以判定 <code>arr[i]</code> 的值比 <code>arr[j]</code> 的值更强：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>&nbsp;<code>|arr[i] - m| &gt; |arr[j]&nbsp;- m|</code></li>\n",
    "\t<li>&nbsp;<code>|arr[i] - m| == |arr[j] - m|</code>，且 <code>arr[i] &gt; arr[j]</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>请返回由数组中最强的 <code>k</code> 个值组成的列表。答案可以以 <strong>任意顺序</strong> 返回。</p>\n",
    "\n",
    "<p><strong>中位数</strong> 是一个有序整数列表中处于中间位置的值。形式上，如果列表的长度为 <code>n</code> ，那么中位数就是该有序列表（下标从 0 开始）中位于 <code>((n - 1) / 2)</code> 的元素。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如 <code>arr =&nbsp;[6, -3, 7, 2, 11]</code>，<code>n = 5</code>：数组排序后得到 <code>arr = [-3, 2, 6, 7, 11]</code> ，数组的中间位置为 <code>m = ((5 - 1) / 2) = 2</code> ，中位数 <code>arr[m]</code> 的值为 <code>6</code> 。</li>\n",
    "\t<li>例如 <code>arr =&nbsp;[-7, 22, 17,&thinsp;3]</code>，<code>n = 4</code>：数组排序后得到&nbsp;<code>arr = [-7, 3, 17, 22]</code> ，数组的中间位置为&nbsp;<code>m = ((4 - 1) / 2) = 1</code> ，中位数 <code>arr[m]</code> 的值为 <code>3</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr = [1,2,3,4,5], k = 2\n",
    "<strong>输出：</strong>[5,1]\n",
    "<strong>解释：</strong>中位数为 3，按从强到弱顺序排序后，数组变为 [5,1,4,2,3]。最强的两个元素是 [5, 1]。[1, 5] 也是正确答案。\n",
    "注意，尽管 |5 - 3| == |1 - 3| ，但是 5 比 1 更强，因为 5 &gt; 1 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr = [1,1,3,5,5], k = 2\n",
    "<strong>输出：</strong>[5,5]\n",
    "<strong>解释：</strong>中位数为 3, 按从强到弱顺序排序后，数组变为 [5,5,1,1,3]。最强的两个元素是 [5, 5]。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr = [6,7,11,7,6,8], k = 5\n",
    "<strong>输出：</strong>[11,8,6,6,7]\n",
    "<strong>解释：</strong>中位数为 7, 按从强到弱顺序排序后，数组变为 [11,8,6,6,7,7]。\n",
    "[11,8,6,6,7] 的任何排列都是正确答案。</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr = [6,-3,7,2,11], k = 3\n",
    "<strong>输出：</strong>[-3,11,2]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 5：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr = [-7,22,17,3], k = 2\n",
    "<strong>输出：</strong>[22,17]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= arr.length &lt;= 10^5</code></li>\n",
    "\t<li><code>-10^5 &lt;= arr[i] &lt;= 10^5</code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= arr.length</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [the-k-strongest-values-in-an-array](https://leetcode.cn/problems/the-k-strongest-values-in-an-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [the-k-strongest-values-in-an-array](https://leetcode.cn/problems/the-k-strongest-values-in-an-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4,5]\\n2', '[1,1,3,5,5]\\n2', '[6,7,11,7,6,8]\\n5']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        result = []\n",
    "        arr.sort()\n",
    "        length = len(arr)\n",
    "        lowindex = 0\n",
    "        highindex = length - 1\n",
    "        low = arr[lowindex]\n",
    "        high = arr[highindex]\n",
    "        mid = arr[(length-1)//2]\n",
    "\n",
    "        while(k>0):\n",
    "            if abs(low-mid) == abs(high-mid):\n",
    "                if low > high:\n",
    "                    result.append(low)\n",
    "                    lowindex += 1\n",
    "                    low = arr[lowindex]\n",
    "                else:\n",
    "                    result.append(high)\n",
    "                    highindex -= 1\n",
    "                    high = arr[highindex]\n",
    "            elif abs(low-mid) > abs(high-mid):\n",
    "                result.append(low)\n",
    "                lowindex += 1\n",
    "                low = arr[lowindex]\n",
    "            else:\n",
    "                result.append(high)\n",
    "                highindex -= 1\n",
    "                high = arr[highindex]\n",
    "            k -= 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        arr.sort()\n",
    "        if len(arr) <= 2:\n",
    "            return arr\n",
    "        mid = (len(arr) - 1) // 2\n",
    "        left, right = 0,  len(arr) - 1\n",
    "        res = [0] * k\n",
    "        i = 0\n",
    "        while i < k:\n",
    "            if left > mid or (right >= mid and arr[mid] - arr[left] <= arr[right] - arr[mid]):\n",
    "                res[i] = arr[right]\n",
    "                right -= 1\n",
    "            else:\n",
    "                res[i] = arr[left]\n",
    "                left += 1\n",
    "            i += 1\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        arr.sort()\n",
    "        idx = (len(arr) - 1) // 2\n",
    "        m = arr[idx]\n",
    "\n",
    "        left, right, count = 0, len(arr) - 1, 0\n",
    "        while count<k:\n",
    "            count += 1\n",
    "            if arr[right] - m >= m - arr[left]:\n",
    "                right -= 1\n",
    "            else:\n",
    "                left += 1\n",
    "\n",
    "        return arr[0:left] + arr[right+1:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        arr.sort()\n",
    "        ans = []\n",
    "        n = len(arr)\n",
    "        m = arr[(n-1)//2]\n",
    "        left,right,i = 0,n-1,0\n",
    "        while left<=right:\n",
    "            if abs(arr[right]-m)>=abs(arr[left]-m):\n",
    "                ans.append(arr[right])\n",
    "                right -= 1\n",
    "            else:\n",
    "                ans.append(arr[left])\n",
    "                left += 1\n",
    "            i += 1\n",
    "        return ans[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "\n",
    "        if len(arr) == k:\n",
    "            return arr\n",
    "        \n",
    "        arr.sort()\n",
    "        keyValue = arr[(len(arr) - 1) // 2]\n",
    "\n",
    "        if arr.count(keyValue) == len(arr):\n",
    "            return [keyValue] * k\n",
    "\n",
    "        while (keyValue in arr):\n",
    "            arr.remove(keyValue)\n",
    "\n",
    "        if len(arr) == k:\n",
    "            return arr\n",
    "        elif (len(arr) < k):\n",
    "            return arr + [keyValue] * (k - len(arr))\n",
    "        \n",
    "        i = 0\n",
    "        j = len(arr) - 1\n",
    "        result = []\n",
    "        while len(result) < k:\n",
    "            if (abs(arr[i] - keyValue) > abs(arr[j] - keyValue)):\n",
    "                result.append(arr[i])\n",
    "                i += 1\n",
    "            elif (abs(arr[i] - keyValue) < abs(arr[j] - keyValue)) or (abs(arr[i] - keyValue) == abs(arr[j] - keyValue)):\n",
    "                result.append(arr[j])\n",
    "                j -= 1\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        arr.sort()\n",
    "        idx = (len(arr) - 1) // 2\n",
    "        m = arr[idx]\n",
    "\n",
    "        left, right, count = 0, len(arr) - 1, 0\n",
    "        res = []\n",
    "        while k:\n",
    "            count += 1\n",
    "            if arr[right] - m >= m - arr[left]:\n",
    "                res.append(arr[right])\n",
    "                right -= 1\n",
    "            else:\n",
    "                res.append(arr[left])\n",
    "                left += 1\n",
    "\n",
    "            if count == k:\n",
    "                break\n",
    "\n",
    "        return arr[0:left] + arr[right+1:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    class Node:\n",
    "        __slots__ = (\"mid\", \"cur\")\n",
    "\n",
    "        def __init__(self, mid, cur):\n",
    "            self.mid = mid\n",
    "            self.cur = cur\n",
    "\n",
    "        def __lt__(self, other):\n",
    "            diff1, diff2 = abs(self.cur - self.mid), abs(other.cur - other.mid)\n",
    "            return diff1 < diff2 or (diff1 == diff2 and self.cur < other.cur)\n",
    "\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        # 注意需要先排序再求中位数\n",
    "        arr = sorted(arr)\n",
    "        mid = arr[(len(arr) - 1) // 2]\n",
    "        return heapq.nlargest(k, arr, key=lambda i: self.Node(mid, i))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        arr.sort()\n",
    "        mid = arr[(len(arr)-1)//2]\n",
    "        left = 0\n",
    "        right = len(arr)-1\n",
    "        new_list = []\n",
    "        while len(new_list) <= k:\n",
    "            if abs(arr[left]-mid) > abs(arr[right]-mid):\n",
    "                new_list.append(arr[left])\n",
    "                left +=1\n",
    "            elif abs(arr[left]-mid) > abs(arr[right]-mid) and arr[left] > arr[right]:\n",
    "                new_list.append(arr[left])\n",
    "                left += 1\n",
    "            else:\n",
    "                new_list.append(arr[right])\n",
    "                right -= 1 \n",
    "        return new_list[0:k]\n",
    "            \n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "                \n",
    "        \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        arr.sort()\n",
    "        if len(arr) <= 2:\n",
    "            return arr\n",
    "        mid = (len(arr) - 1) // 2\n",
    "        left, right = mid - 1,  mid + 1\n",
    "        res = [0] * len(arr)\n",
    "        res[-1] = arr[mid]\n",
    "        i = len(arr) - 2\n",
    "        while left >= 0 or right < len(arr):\n",
    "            if left < 0 or (right < len(arr) and arr[mid] - arr[left] > arr[right] - arr[mid]):\n",
    "                res[i] = arr[right]\n",
    "                right += 1\n",
    "            else:\n",
    "                res[i] = arr[left]\n",
    "                left -= 1\n",
    "            i -= 1\n",
    "        print(res)\n",
    "        return res[:k]\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        arr.sort()\n",
    "        mid = arr[(len(arr) - 1) // 2]\n",
    "        temp = [abs(i - mid) for i in arr]\n",
    "        index = sorted(range(len(temp)), key=lambda k: temp[k])\n",
    "        res = []\n",
    "        print(index)\n",
    "        print(k)\n",
    "        for i in range(len(index)-1 , len(index)-k-1, -1):\n",
    "            res.append(arr[index[i]])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        def cmp(a,b):\n",
    "            if abs(a)>abs(b):\n",
    "                return 1\n",
    "            if abs(a)==abs(b) and a>b:\n",
    "                return 1\n",
    "            return -1\n",
    "            \n",
    "        arr.sort()\n",
    "        mid = arr[(len(arr)-1)//2]\n",
    "        temp = [(ele-mid) for ele in arr]\n",
    "        temp.sort(key=functools.cmp_to_key(cmp),reverse=True)\n",
    "        return [ele + mid for ele in temp[:k]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        n = len(arr)\n",
    "        arr.sort()\n",
    "        m = arr[(n - 1) // 2]\n",
    "        # print(m)\n",
    "        arr.sort(key=lambda x:abs(x-m))\n",
    "        return arr[n-k:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "      arr.sort()\n",
    "      n = len(arr)\n",
    "      m = arr[(n - 1) // 2]\n",
    "\n",
    "      heap = []\n",
    "      for i in range(n):\n",
    "        if len(heap) < k:\n",
    "          heapq.heappush(heap, (abs(arr[i] - m), arr[i]))\n",
    "        elif abs(arr[i] - m) > heap[0][0] or (abs(arr[i] - m) == heap[0][0] and arr[i] > heap[0][1]):\n",
    "          heapq.heapreplace(heap, (abs(arr[i] - m), arr[i]))\n",
    "      \n",
    "      return [i[1] for i in heap]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        idx = sorted(range(len(arr)),key = lambda i:arr[i])\n",
    "        m = arr[idx[(len(arr)-1)//2]]\n",
    "        left,right = 0,len(arr)-1\n",
    "        ans = []\n",
    "        for _ in range(k):\n",
    "            if abs(arr[idx[right]]-m) >= abs(arr[idx[left]]-m):\n",
    "                ans.append(arr[idx[right]])\n",
    "                right -= 1\n",
    "            else:\n",
    "                ans.append(arr[idx[left]])\n",
    "                left += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cmp_to_key\n",
    "class Solution:\n",
    "\n",
    "    def getStrongest(self,arr: List[int], k: int) -> List[int]:\n",
    "        arr.sort()\n",
    "        mid_number=arr[int((len(arr)-1)/2)]\n",
    "\n",
    "        def customsorting(x,y):\n",
    "            x_mid=abs(x-mid_number)\n",
    "            y_mid=abs(y-mid_number)\n",
    "            if  x_mid> y_mid or ((x_mid == y_mid) and (x > y)):\n",
    "                return -1 #-1表示x应该在y前面\n",
    "            else:\n",
    "                return 0\n",
    "\n",
    "        arr.sort(key=cmp_to_key(customsorting))\n",
    "        return arr[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cmp_to_key\n",
    "class Solution:\n",
    "\n",
    "    def getStrongest(self,arr: List[int], k: int) -> List[int]:\n",
    "        arr.sort()\n",
    "        mid_number=arr[int((len(arr)-1)/2)]\n",
    "\n",
    "        def customsorting(x,y):\n",
    "            x_mid=abs(x-mid_number)\n",
    "            y_mid=abs(y-mid_number)\n",
    "            if  x_mid> y_mid or ((x_mid == y_mid) and (x > y)):\n",
    "                return -1 #-1表示x应该在y前面\n",
    "            else:\n",
    "                return 0\n",
    "\n",
    "        arr=sorted(arr,key=cmp_to_key(customsorting))\n",
    "        return arr[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cmp_to_key\n",
    "import math\n",
    "class Solution:\n",
    "    def getStrongest(self, nums, k):\n",
    "        nums.sort()\n",
    "        m = nums[int((len(nums) - 1) / 2)]\n",
    "        def cmp(a, b):\n",
    "            if math.fabs(a-m) == math.fabs(b-m):\n",
    "                return a - b\n",
    "            else:\n",
    "                return math.fabs(a-m) - math.fabs(b-m)\n",
    "\n",
    "        nums = sorted(nums, key=cmp_to_key(cmp), reverse=True)\n",
    "        return nums[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        pq=[]\n",
    "        sarr=sorted(arr)\n",
    "        n=len(arr)\n",
    "        m=sarr[(n-1)//2]\n",
    "        for x in arr:\n",
    "            heappush(pq,(abs(x-m),x))\n",
    "            if len(pq)>k:\n",
    "                heappop(pq)\n",
    "        ans=[]\n",
    "        while pq:\n",
    "            _,x=heappop(pq)\n",
    "            ans.append(x)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Item:\n",
    "    key = 0\n",
    "    def get_key(self):\n",
    "        return Item.key\n",
    "    def set_key(self, x):\n",
    "        Item.key = x\n",
    "\n",
    "    def __init__(self, x):\n",
    "        self.num = x\n",
    "    def __lt__(self, other):\n",
    "        return abs(self.num - Item.key) < abs(other.num - Item.key) or (abs(other.num - Item.key) == abs(self.num - Item.key) and self.num < other.num)\n",
    "    def __repr__(self):\n",
    "        return str(self.num)\n",
    "\n",
    "from heapq import heappush, heappop      \n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        arr = sorted(arr)\n",
    "        m = arr[(len(arr) - 1) // 2]\n",
    "        Item.key = m\n",
    "        heap = []\n",
    "        for num in arr:\n",
    "            item = Item(num)\n",
    "            heappush(heap, item)\n",
    "            if len(heap) > k:\n",
    "                heappop(heap)\n",
    "            # print(heap)\n",
    "        ans = []\n",
    "        while heap:\n",
    "            ans.append(heappop(heap).num)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:       \n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        arr.sort()\n",
    "        m = arr[int((len(arr)-1)/2)]\n",
    "        sorted_arr = []\n",
    "        # sorted_arr.append(m)\n",
    "        def cmp_custom(n1,n2):\n",
    "            if abs(n1 - m) > abs(n2 - m):\n",
    "                return -1\n",
    "            elif (abs(n1 - m) == abs(n2 - m)) and (n1 > n2):\n",
    "                return -1\n",
    "            else:\n",
    "                return 1\n",
    "        # offset = 1\n",
    "        # while len(sorted_arr) != len(arr):\n",
    "        #     sorted_arr.insert(0,arr[int((len(arr)-1)/2)+offset])\n",
    "        #     if len(sorted_arr) == len(arr):\n",
    "        #         break\n",
    "        #     sorted_arr.insert(0,arr[int((len(arr)-1)/2)-offset])\n",
    "        #     offset += 1\n",
    "\n",
    "        # for n1 in arr:\n",
    "        #     if len(sorted_arr) == 0:\n",
    "        #        sorted_arr.append(n1)\n",
    "        #     else:\n",
    "        #         flag = 0\n",
    "        #         for i in range(0,len(sorted_arr)):\n",
    "        #             n2 = sorted_arr[i]\n",
    "        #             if cmp_custom(n1,n2,m) > 0:\n",
    "        #                 sorted_arr.insert(i,n1)\n",
    "        #                 flag = 1\n",
    "        #                 break\n",
    "        #         if flag == 0:\n",
    "        #             sorted_arr.append(n1)\n",
    "        sorted_arr = sorted(arr,key=functools.cmp_to_key(cmp_custom))\n",
    "        res = []\n",
    "        for i in range(0,k):\n",
    "            res.append(sorted_arr[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        l=sorted(arr)\n",
    "        if len(arr)&1:\n",
    "            x=l[len(arr)//2]\n",
    "        else:\n",
    "            x=l[len(arr)//2-1]\n",
    "\n",
    "        def comp(a,b):\n",
    "            if abs(b-x)-abs(a-x)>0:\n",
    "                return 1\n",
    "            elif abs(b-x)-abs(a-x)<0:\n",
    "                return -1\n",
    "            else:\n",
    "                if b>a:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return -1\n",
    "\n",
    "        return sorted(arr,key=functools.cmp_to_key(comp))[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def getMidNum(self, arr):\n",
    "        arrNew = arr.copy()\n",
    "        arrNew.sort()\n",
    "        mid = (len(arr) - 1) // 2\n",
    "        return arrNew[mid]\n",
    "\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        m = self.getMidNum(arr)\n",
    "\n",
    "        def myCmp(x, y):\n",
    "            if x == y:\n",
    "                return 0\n",
    "\n",
    "            if abs(x - m) < abs(y - m):\n",
    "                return -1\n",
    "            elif abs(x - m) == abs(y - m):\n",
    "                if x < y:\n",
    "                    return -1\n",
    "                else:\n",
    "                    return 1\n",
    "            else:\n",
    "                return 1\n",
    "\n",
    "        arr.sort(key=cmp_to_key(myCmp), reverse=True)\n",
    "        return arr[:k]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        arr.sort()\n",
    "        m = arr[(len(arr)-1)//2]\n",
    "        import heapq\n",
    "        return heapq.nlargest(k, arr, key=lambda x: (abs(x-m), x))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        arr.sort()\n",
    "        n = len(arr)\n",
    "        mid = arr[(n - 1) // 2]\n",
    "        powers = []\n",
    "        for i in range(n):\n",
    "            powers.append((abs(arr[i] - mid), 1 if arr[i] - mid > 0 else 0, arr[i]))\n",
    "        powers.sort(reverse=True)\n",
    "        \n",
    "        ans = []\n",
    "        for i in range(k):\n",
    "            _, _, v = powers[i]\n",
    "            ans.append(v)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    median = 0\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "\n",
    "    def __lt__(self, b):\n",
    "        dis_a = abs(self.val - Node.median)\n",
    "        dis_b = abs(b.val - Node.median)\n",
    "\n",
    "        return dis_a < dis_b if dis_a != dis_b else self.val < b.val\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        arr.sort()\n",
    "\n",
    "        n = len(arr)\n",
    "\n",
    "        median = arr[(n-1)//2]\n",
    "        Node.median = median\n",
    "\n",
    "        print('median ', median)\n",
    "        a = [] # 小顶堆， 堆的元素个数为k，堆顶元素最弱\n",
    "\n",
    "        for i in range(n):\n",
    "            if len(a) < k:\n",
    "                heapq.heappush(a, Node(arr[i]))\n",
    "            elif len(a) >0 and a[0] < Node(arr[i]):\n",
    "                heapq.heappop(a)\n",
    "                heapq.heappush(a, Node(arr[i]))\n",
    "        \n",
    "\n",
    "       \n",
    "\n",
    "        return[x.val for x in a] # 注意返回的变量类型不是 Node\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        s=sorted(arr)\n",
    "        n=len(arr)\n",
    "        m=s[(n-1)//2]\n",
    "        arr.sort(key=lambda x:(abs(x-m),x),reverse=True)\n",
    "        return arr[:k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        arr.sort()\n",
    "        n = len(arr)\n",
    "        mid = arr[(n-1)//2]\n",
    "        res = []\n",
    "        m = (max(abs(arr[-1]-mid),abs(arr[0]-mid))+1)\n",
    "        temp = [[] for i in range(m)]\n",
    "        for i in arr:\n",
    "            temp[abs(i-mid)].append(i)\n",
    "        for i in range(m-1,-1,-1):\n",
    "            res += sorted(temp[i],reverse=True)\n",
    "        return res[0:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        arr.sort()\n",
    "        n = len(arr)\n",
    "        mid = arr[(n-1)//2]\n",
    "        res = []\n",
    "        m = (max(abs(arr[-1]-mid),abs(arr[0]-mid))+1)\n",
    "        temp = [[] for i in range(m)]\n",
    "        for i in arr:\n",
    "            temp[abs(i-mid)].append(i)\n",
    "        for i in range(m-1,-1,-1):\n",
    "            res += sorted(temp[i],reverse=True)\n",
    "        return res[0:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        arr.sort()\n",
    "        m = arr[int((len(arr) - 1)/2)]\n",
    "        def compare(a, b):\n",
    "            if abs(a-m) > abs(b - m):\n",
    "                return 1\n",
    "            if abs(a-m) == abs(b - m):\n",
    "                if a > b:\n",
    "                    return 1\n",
    "                if a == b:\n",
    "                    return 0\n",
    "            return -1\n",
    "        from functools import cmp_to_key\n",
    "        arr.sort(key=cmp_to_key(compare), reverse=True)\n",
    "        return arr[:k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        arr.sort()\n",
    "        mid = arr[(len(arr)-1)//2]\n",
    "        def cmp(n1, n2):\n",
    "            d1 = abs(n1-mid)\n",
    "            d2 = abs(n2-mid)\n",
    "            if d1 != d2:\n",
    "                return d1 - d2\n",
    "            else:\n",
    "                return n1 - n2\n",
    "        arr.sort(key=functools.cmp_to_key(cmp), reverse=True)\n",
    "        return arr[:k]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        n = len(arr)\n",
    "        arr.sort()\n",
    "        mid = arr[(n-1)//2]\n",
    "        def cmp(i, j):\n",
    "            if i == j: return 0\n",
    "            absi, absj = abs(i-mid), abs(j-mid)\n",
    "            if absi > absj:\n",
    "                return 1\n",
    "            elif absi == absj and i > j:\n",
    "                return 1\n",
    "            else:\n",
    "                return -1\n",
    "        \n",
    "        arr.sort(key=cmp_to_key(cmp))\n",
    "        return arr[-k:]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr, k):\n",
    "        arr.sort()\n",
    "        mid = arr[(len(arr)-1)//2]\n",
    "        arr_dict = {}\n",
    "        nums = []\n",
    "        for i in range(len(arr)):\n",
    "            arr_dict[arr[i]] = abs(arr[i] - mid)\n",
    "\n",
    "        left = 0\n",
    "        right = len(arr) - 1\n",
    "        index = 0\n",
    "        while index != k:\n",
    "            if arr_dict[arr[left]] > arr_dict[arr[right]]:\n",
    "                nums.append(arr[left])\n",
    "                left += 1\n",
    "            else:\n",
    "                nums.append(arr[right])\n",
    "                right -= 1\n",
    "            index += 1\n",
    "\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        arr = sorted(arr)\n",
    "        mid_val = arr[(len(arr)- 1) // 2]\n",
    "\n",
    "        arr = [(abs(a-mid_val), a) for a in arr]\n",
    "        arr = sorted(arr)\n",
    "        return [a[1] for a in arr[-k:]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        arr.sort()\n",
    "        m=arr[(len(arr)-1)//2]\n",
    "        #print(m)\n",
    "        arr.sort(key=lambda x:(abs(x-m),x))\n",
    "        #print(arr)\n",
    "        return arr[-k:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        m = sorted(arr)[(len(arr) - 1) // 2]\n",
    "        return sorted(arr, reverse=True, key=lambda x: (abs(x - m), x))[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        n = len(arr)\n",
    "        # 先排序求中位数\n",
    "        arr = sorted(arr)\n",
    "        mid = arr[(n - 1) // 2]\n",
    "\n",
    "        def mykey(x):\n",
    "            # 自定义最强排序的key函数\n",
    "            # 注意py 3不同于其他语言的传入两个参数的自定义比较函数\n",
    "            # 此处的意思代表先按照abs升序排列, 相等情况下再按照自身的值的升序排列\n",
    "            return (abs(x - mid), x)\n",
    "\n",
    "        # 按照最强排序后取最后的k个即为所求\n",
    "        arr = sorted(arr, key=mykey)\n",
    "        return arr[n - k:]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        n = len(arr)\n",
    "        # 先排序求中位数\n",
    "        arr = sorted(arr)\n",
    "        mid = arr[(n - 1) // 2]\n",
    "\n",
    "        def mykey(x):\n",
    "            # 自定义最强排序的key函数\n",
    "            # 注意py 3不同于其他语言的传入两个参数的自定义比较函数\n",
    "            # 此处的意思代表先按照abs升序排列, 相等情况下再按照自身的值的升序排列\n",
    "            return (abs(x - mid), x)\n",
    "\n",
    "        # 按照最强排序后取最后的k个即为所求\n",
    "        arr = sorted(arr, key=mykey)\n",
    "        return arr[n - k:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        arr.sort()\n",
    "        m=arr[(len(arr)-1)//2]\n",
    "        arr.sort(key=lambda x:(abs(x-m),x),reverse=True)\n",
    "        return arr[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        arr.sort()\n",
    "        mid = arr[(len(arr) - 1) // 2]\n",
    "        arange = arr[-1] - arr[0]\n",
    "\n",
    "        if arange == 0:\n",
    "            return arr[:k]\n",
    "        arr = sorted([(abs(x - mid) + (x - arr[0]) / arange, x) for x in arr], reverse=True)\n",
    "        return [x[1] for x in arr[:k]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        arr.sort()\n",
    "        n = len(arr)\n",
    "        median = arr[(n-1)//2]\n",
    "        lst = [(abs(num-median), num) for num in arr]\n",
    "        lst.sort(reverse = True)\n",
    "        return [x[1] for x in lst[:k]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        arr.sort()\n",
    "        mid = arr[(len(arr)-1)//2]\n",
    "        return nlargest(k, arr,key=lambda x:[abs(x-mid),x])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "#         arr.sort()\n",
    "#         m = arr[(len(arr)-1)//2]\n",
    "#         nL = []\n",
    "#         for i, num in zip(range(len(arr)), arr):\n",
    "#             nL.append((abs(num -m), i))\n",
    "#         def cmp(x):\n",
    "#             return x[0], arr[x[1]]\n",
    "#         nL.sort(key = cmp, reverse = True)\n",
    "#         # nL.sort(key = lambda x: (x[0], arr[x[1]]), reverse = True)\n",
    "#         res = [arr[nL[i][1]] for i in range(k)]\n",
    "#         return res\n",
    "\n",
    "# 先找出中位数，然后创建元组列表进行排序，法则是先比较第一个元素的大小，然后再比较arr[i]的大小\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        arr.sort()\n",
    "        m = arr[(len(arr)-1)//2]\n",
    "        def cmp(x):\n",
    "            return abs(x-m), x\n",
    "        arr.sort(key = cmp, reverse = True)\n",
    "        # nL.sort(key = lambda x: (x[0], arr[x[1]]), reverse = True)\n",
    "        return arr[:k]\n",
    "\n",
    "# 先找出中位数，然后创建元组列表进行排序，法则是先比较第一个元素的大小，然后再比较arr[i]的大小\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        n, sarr = len(arr), sorted(arr)\n",
    "        m = n // 2 - 1 if n % 2 == 0 else n // 2\n",
    "        medium = sarr[m]\n",
    "        dists = []\n",
    "        for i, v in enumerate(arr):\n",
    "            dist = abs(v - medium)\n",
    "            dists.append((dist, v))\n",
    "\n",
    "        dists = sorted(dists, reverse=True)\n",
    "\n",
    "        return [d[1] for d in dists[:k]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        arr.sort()\n",
    "        m = arr[(len(arr) - 1) // 2]\n",
    "        arr.sort(key=lambda x: (abs(x - m), x), reverse=True)\n",
    "        return arr[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "#         arr.sort()\n",
    "#         m = arr[(len(arr)-1)//2]\n",
    "#         nL = []\n",
    "#         for i, num in zip(range(len(arr)), arr):\n",
    "#             nL.append((abs(num -m), i))\n",
    "#         def cmp(x):\n",
    "#             return x[0], arr[x[1]]\n",
    "#         nL.sort(key = cmp, reverse = True)\n",
    "#         # nL.sort(key = lambda x: (x[0], arr[x[1]]), reverse = True)\n",
    "#         res = [arr[nL[i][1]] for i in range(k)]\n",
    "#         return res\n",
    "\n",
    "# 先找出中位数，然后创建元组列表进行排序，法则是先比较第一个元素的大小，然后再比较arr[i]的大小\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        arr.sort()\n",
    "        m = arr[(len(arr)-1)//2]\n",
    "        # def cmp(x):\n",
    "        #     return abs(x-m), x\n",
    "        # arr.sort(key = cmp, reverse = True)\n",
    "        arr.sort(key = lambda x: (abs(x-m), x), reverse =True)\n",
    "        return arr[:k]\n",
    "\n",
    "# 先找出中位数，然后创建元组列表进行排序，法则是先比较第一个元素的大小，然后再比较arr[i]的大小\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        n=len(arr)\n",
    "        arr.sort()\n",
    "        m=arr[(n-1)//2]\n",
    "        data=[(abs(x-m),x) for x in arr]\n",
    "        data.sort(reverse=True)\n",
    "        return [x for dif,x in data[:k]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        \n",
    "        from collections import defaultdict\n",
    "        hs = defaultdict(list)\n",
    "        arr.sort()\n",
    "        if len(arr)%2:\n",
    "            median = arr[len(arr)//2]\n",
    "        else:\n",
    "            median = arr[(len(arr)-1)//2]\n",
    "        for ele in arr:\n",
    "            hs[abs(ele-median)].append(ele)\n",
    "        key_s = sorted(list(hs.keys()),reverse=True)\n",
    "        res = []\n",
    "        for key in key_s:\n",
    "            for ele in sorted(hs[key],reverse=True):\n",
    "                res.append(ele)\n",
    "                if len(res)==k:\n",
    "                    return res\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        n = len(arr)\n",
    "        # 先排序求中位数\n",
    "        arr.sort()\n",
    "        mid = arr[(n - 1) // 2]\n",
    "\n",
    "        def mykey(x):\n",
    "            # 自定义最强排序的key函数\n",
    "            # 注意py 3不同于其他语言的传入两个参数的自定义比较函数\n",
    "            # 此处的意思代表先按照abs升序排列, 相等情况下再按照自身的值的升序排列\n",
    "            return (abs(x - mid), x)\n",
    "\n",
    "        # 按照最强排序后取最后的k个即为所求\n",
    "        arr = sorted(arr, key=mykey)\n",
    "        return arr[n - k:]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        m = median_low(arr)\n",
    "        arr.sort(key=lambda n:(abs(n - m), n))\n",
    "        return arr[-k:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "     arr.sort()\n",
    "     size=len(arr)\n",
    "     mid = arr[int((size - 1) / 2)]\n",
    "     arr.sort(key = lambda x:(abs(x-mid),x))\n",
    "     return arr[-k:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        arr.sort()\n",
    "        n = len(arr)\n",
    "        # if n % 2 == 1:\n",
    "        #     mid = arr[n//2]\n",
    "        # else:\n",
    "        #     mid = (arr[n//2-1] + arr[n//2]) / 2\n",
    "        mid = arr[(n-1) // 2]\n",
    "        arr.sort(key = lambda x: (abs(x-mid), x), reverse=True)\n",
    "        return arr[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        def hs(x):\n",
    "            return (abs(m - x), x)\n",
    "\n",
    "        m = sorted(arr)[(len(arr) - 1) // 2]\n",
    "        arr.sort(key=hs)\n",
    "        return arr[-k:]\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\r\n",
    "        arr.sort()\r\n",
    "        n = len(arr)\r\n",
    "        # 自定义中位数，与通常理解的不一样\r\n",
    "        median = arr[(n - 1) // 2]\r\n",
    "        lis = []\r\n",
    "        for val in arr:\r\n",
    "            lis.append((abs(val - median), val))\r\n",
    "        lis.sort()\r\n",
    "        ans = []\r\n",
    "        for i in range(n - k, n):\r\n",
    "            ans.append(lis[i][1])\r\n",
    "        return(ans)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        mid = sorted(arr)[(len(arr) - 1) // 2]\n",
    "        abs_num = sorted(((abs(num - mid), num) for i, num in enumerate(arr)), reverse=True)\n",
    "        return [i for _, i in abs_num[:k]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        arr.sort()\n",
    "        m = arr[(len(arr) - 1) // 2]\n",
    "        arr = [(abs(n - m), n) for n in arr]\n",
    "        arr.sort()\n",
    "        arr = [n for a, n in arr[-k:]]\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        tmp = arr\n",
    "        tmp.sort()\n",
    "        size = len(tmp)\n",
    "        m = tmp[int((size - 1) / 2)]\n",
    "        if size >= 2 * k:\n",
    "            test_v = tmp[:k] + tmp[-k:]\n",
    "        else:\n",
    "            test_v = arr\n",
    "        diff = [(abs(x - m), x) for x in test_v]\n",
    "        diff.sort(key=lambda x: (x[0] + x[1] / 1000000) , reverse=True)\n",
    "        vd = [x[1] for x in diff[:k]]\n",
    "        return vd\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        # 二分\n",
    "\n",
    "        n = len(arr)\n",
    "        arr.sort()\n",
    "        mid = arr[(n-1)//2]\n",
    "\n",
    "        arr = sorted(arr, key = lambda x: (abs(mid-x),x))\n",
    "        return arr[n-k:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        n = len(arr)\n",
    "        ans=[]\n",
    "        arr.sort()\n",
    "        m=arr[(n - 1) // 2]\n",
    "        def mykey(x):\n",
    "            return (abs(x-m),x)\n",
    "        arr = sorted(arr,key = mykey)\n",
    "        return arr[n-k:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        arr.sort()\n",
    "        mid = arr[(len(arr)-1)//2]\n",
    "        return sorted(arr,key=lambda x:[abs(x-mid),x])[-k:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        n = len(arr)\n",
    "        mid = sorted(arr)[(n-1)//2]\n",
    "        return sorted(arr,key=lambda x:[abs(x-mid),x])[-k:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        n = len(arr)\n",
    "        arr = sorted(arr)\n",
    "        mid = arr[(n - 1) // 2]\n",
    "        arr = sorted(arr, key = lambda x: (abs(x - mid), x))\n",
    "        return arr[n - k:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        n = len(arr)\n",
    "        arr = sorted(arr)\n",
    "        mid = arr[(n - 1) // 2]\n",
    "\n",
    "        def mykey(x):\n",
    "            return (abs(x - mid), x)\n",
    "\n",
    "        arr = sorted(arr, key=mykey)\n",
    "        return arr[n - k:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        n = len(arr)\n",
    "        arr = sorted(arr)\n",
    "        mid = arr[(n - 1) // 2]\n",
    "        arr = sorted(arr, key=lambda x:(abs(x - mid), x))\n",
    "        return arr[n - k:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        from sortedcontainers import SortedList\n",
    "        n = len(arr)\n",
    "        arr.sort()\n",
    "        med = arr[(n-1)//2]\n",
    "        str_arr = SortedList(arr, key=lambda x: (-abs(x-med), -x))\n",
    "        #print(med)\n",
    "        #print(str_arr)\n",
    "        return list(str_arr[:k])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        sorted_arr = sorted(arr)\n",
    "        mididx = (len(sorted_arr)-1)//2\n",
    "        mid = sorted_arr[mididx]\n",
    "\n",
    "        new_arr = [(abs(i-mid), i) for i in arr]\n",
    "\n",
    "        def cmp_temp(x, y):\n",
    "            if (x[0] == y[0]):\n",
    "                return y[1] - x[1]\n",
    "            else:\n",
    "                return y[0] - x[0]\n",
    "\n",
    "        new_arr = sorted(new_arr, key=cmp_to_key(cmp_temp))\n",
    "\n",
    "        res = [new_arr[i][1] for i in range(k)]\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        n = len(arr)\n",
    "        arr.sort()\n",
    "        middle = arr[int((n - 1) / 2)]\n",
    "\n",
    "        val = []  #强度\n",
    "        for i in range(n):\n",
    "            val.append(abs(arr[i] - middle))\n",
    "\n",
    "        dic = dict(zip(arr, val))\n",
    "        res = sorted(arr, key=lambda x: dic[x])\n",
    "        res = res[::-1]\n",
    "        return res[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        arr.sort()\n",
    "        n = len(arr)\n",
    "        m = arr[(n - 1) // 2]\n",
    "        arr.sort(key = lambda x:(-abs(x - m), -x))\n",
    "        return arr[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        arr = sorted(arr)\n",
    "        l = len(arr)\n",
    "        m = arr[(l - 1) // 2]\n",
    "        \n",
    "        res = []\n",
    "        for num in arr:\n",
    "            heapq.heappush(res, (-abs(num - m), -num))\n",
    "        \n",
    "        ans = []\n",
    "        for i in range(k):\n",
    "            _, num = heapq.heappop(res)\n",
    "            ans.append(-num)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        middle = list(sorted(arr))[(len(arr)-1)//2]\n",
    "        gains = []\n",
    "        for i in arr:\n",
    "            heapq.heappush(gains,[abs(i-middle),i])\n",
    "\n",
    "        result = []\n",
    "        for i in heapq.nlargest(k,gains):\n",
    "            result.append(i[1])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        n = len(arr)\n",
    "        arr.sort()\n",
    "        mid = arr[(n-1)//2]\n",
    "        arr.sort(key=lambda x: [-abs(x-mid), -x])\n",
    "        return arr[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        from heapq import heappush, heappop\n",
    "        q, N, res = [], len(arr), []\n",
    "        arr.sort()\n",
    "        m = arr[(N - 1)//2]\n",
    "\n",
    "        for a in arr:\n",
    "            heappush(q, [-abs(a - m), -a])\n",
    "\n",
    "        while k > 0:\n",
    "            res.append(-heappop(q)[1])\n",
    "            k -= 1\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        count = {}\n",
    "        for i in arr:\n",
    "            count[i] = count.get(i,0)+1\n",
    "        cnt = 0\n",
    "        mididx = (len(arr)-1)//2\n",
    "        m = -1\n",
    "        for key in sorted(count.keys()):\n",
    "            if cnt+count.get(key)<mididx+1:\n",
    "                cnt += count.get(key)\n",
    "            else:\n",
    "                m = key\n",
    "                break\n",
    "        # pq = [-1] * k\n",
    "        # cnt = 0\n",
    "        # def comp(i,j):\n",
    "        #     x,y = arr[i],arr[j]\n",
    "        #     if x==y:\n",
    "        #         return 0\n",
    "        #     elif abs(x-m)>abs(y-m) or (abs(x-m)==abs(y-m) and x>y):\n",
    "        #         return 1\n",
    "        #     else:\n",
    "        #         return -1\n",
    "        # for i in range(len(arr)):\n",
    "        #     change = 0\n",
    "        #     if cnt < k:\n",
    "        #         pq[cnt] = i\n",
    "        #         cnt += 1\n",
    "        #         change = 1\n",
    "        #     else:\n",
    "        #         z = comp(pq[0],i)\n",
    "        #         if z==-1:\n",
    "        #             pq[0] = pq[cnt-1]\n",
    "        #             pq[cnt-1] = i\n",
    "        #             change = 1\n",
    "        #     if change:\n",
    "        #         v = cnt-1\n",
    "        #         while v > 0:\n",
    "        #             j = v\n",
    "        #             while j > 0:\n",
    "        #                 z = comp(pq[j],pq[(j-1)//2])\n",
    "        #                 if z==-1:\n",
    "        #                     pq[j],pq[(j-1)//2] = pq[(j-1)//2],pq[j]\n",
    "        #                     j = (j-1)//2\n",
    "        #                 else:\n",
    "        #                     break\n",
    "        #             v -= 1\n",
    "        # return [arr[i] for i in pq]\n",
    "        tmp = [(abs(i-m),i) for i in arr]\n",
    "        return [x[1] for x in sorted(tmp,reverse=True)[:k]]\n",
    "        \n",
    "        \n",
    "'''\n",
    "[1,2,3,4,5]\n",
    "2\n",
    "[1,1,3,5,5]\n",
    "2\n",
    "[6,7,11,7,6,8]\n",
    "5\n",
    "[-7,22,17,3]\n",
    "2\n",
    "[6,-3,7,2,11]\n",
    "3\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        arr.sort()\n",
    "        m=arr[(len(arr)-1)//2]\n",
    "        res=[]\n",
    "        for i in arr:\n",
    "            res.append([i,abs(i-m)])\n",
    "        res=sorted(res,key=lambda x:x[0],reverse=True)\n",
    "        res=sorted(res,key=lambda x:x[1],reverse=True)\n",
    "        return [i[0] for i in res[:k]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        arr.sort()\n",
    "        m=arr[(len(arr)-1)//2]\n",
    "        res=[]\n",
    "        for i in arr:\n",
    "            res.append([i,abs(i-m)])\n",
    "        res=sorted(res,key=lambda x:x[0],reverse=True)\n",
    "        res=sorted(res,key=lambda x:x[1],reverse=True)\n",
    "        return [i[0] for i in res[:k]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getStrongest(self, arr: List[int], k: int) -> List[int]:\n",
    "        arr.sort()\n",
    "        m=arr[(len(arr)-1)//2]\n",
    "        res=[]\n",
    "        for i in arr:\n",
    "            res.append([i,abs(i-m)])\n",
    "        res=sorted(res,key=lambda x:x[0],reverse=True)\n",
    "        res=sorted(res,key=lambda x:x[1],reverse=True)\n",
    "        return [i[0] for i in res[:k]]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
